System Model

• 系統由資源組成。
• 資源有分很多種類，像是CPU cycle、memory space、I/O devices等。
• 每個資源類型都有一定的量的instances。
• 每個process在採用資源時，都有一定的執行順序：

1. request-要求
2. use-使用
3. release-釋放

Deadlock Characterization

• 要造成deadlock的發生，需同時滿足以下四種條件：

1. Mutual exclusion：在一個時間內，只能有一個process可以使用資源。
2. Hold and wait：一個process需要很多資源時，先得到一個資源後就先持有住，然後等待一個個的資源都取好後，再繼續執行下去。
3. No preemption：當一個process取得資源後，需要它自己自願將資源放進去，不可以中斷，否則deadlock便不會產生。
4. Circular wait：在系統中存在一組Process，且每個之間都處於前一個process在等待下一個process的資源的狀態，第一個等待第二個，最後一個又再等待第一個的資源，如此一來形成一個cycle，也就成了circular wait的情形。

Deadlock with Mutex Locks

• Deadlocks可以透過system calls、locking等情形發生。

Resource-Allocation Graph

• 由vertices V跟edges E所組成。
• V總共被分成兩種類型：

1. P = {P1,P2,....,Pn}，在系統中由所有process所組成。
2. R = {R1,R2,....,Rm}，在系統中由所有資源類型所組成。

• request edge：Pi向Rj請求資源。
• assignment edge：Rj分配資源給Pi。

Basic Facts

• 如果graph沒有cycle的產生的話，就不會有deadlock。
• 如果graph有cycle的產生，則有兩種情況：

1. 只有一個instance在一個資源種類裡的話，一定有deadlock的產生。
2. 如果有很多instance在一個資源種類裡的話，是有可能會產生deadlock；因為有些instances可能會被釋放出來，所以就有可能不會形成deadlock。

Methods for Handling Deadlocks

• 為了確保系統永遠不會進入deadlock的狀態，所以有了以下四個對策方法：

1. Deadlock prevention
2. Deadlock avoidence
3. Deadlock Detection：允許deadlock的發生，但是要可以偵測到它，並且recover它。
4. Deadlock ignore：忽視並假裝並沒有deadlock的發生。這種方式被大多數系統所採用，如UNIX。

• 第1、2、3種方法都很耗費系統資源，但理論上很重要，只是當實際操作中，如果需要話費很多時間處理的話，最中可能會採取取消程式的方式解決。

Deadlock Prevention

• 防止以下四種情形的產生：

1. Mutual Exclusion：不要求可以共享資源，或是持有不可共享的資源；但不太能被防止，因為它一次就是只能給一個process使用。
2. Hold and wait：如果有process請求資源的話，就一次全部給它，如此一來就不會有等待的情況發生。
3. No preemption：就是讓別人中斷此資源，如此一來要重新開始的話就會變得複雜，在這邊是可以做到限制的，但缺點是效率會很差。
4. Circular Wait：給每個資源一個固定的順序，讓process依照順序去取得資源，如此一來就不會發生被其他process佔據資源的情形，也就不會形成cycle，但缺點就是對系統的負擔很大。